perm filename 1[00,BGB] blob
sn#075330 filedate 1973-11-30 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00016 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 ~F8DATA STRUCTURE: BASICS.
C00007 00003 DATA STRUCTURE: KINDS OF NODES.
C00012 00004 DATA STRUCTURE: LINK AND DATUM NAMES.
C00015 00005 DATA STRUCTURE: THE RINGS, TREES, LISTS AND ARRAYS.
C00018 00006 DATA STRUCTURE: THE RINGS, TREES, LISTS AND ARRAYS.
C00022 00007 DATA STRUCTURE: TYPE BITS.
C00026 00008 DATA STRUCTURE: RELLOCATION BITS.
C00028 00009 1. VECTOR & 2. ARC NODE FORMAT.
C00033 00010 3. POLYGON NODE FORMAT.
C00037 00011 4. SHAPE NODE FORMAT.
C00042 00012 5. LEVEL NODE FORMAT.
C00046 00013 6. IMAGE NODE FORMAT.
C00050 00014 7. FILM NODE FORMAT.
C00053 00015 8. EMPTY NODE FORMAT.
C00056 00016 DATA STRUCTURE: IMAGE ARRAYS.
C00060 ENDMK
C⊗;
~F8DATA STRUCTURE: BASICS.
The two generic data structures of CRE are arrays and nodes;
there are five kinds of arrays and eight kinds of nodes. The node
structures to be discussed are implemented as seven word fixed sized
blocks in a fashion usual to graphics and simulation; an
introduction to this technology can be found in Knuth [4]. The
language of implementation is PDP-10 machine code via the FAIL
assembler.
The whole nodal structure in CRE represents a sequence in
time of video intensity contour maps. Such contour maps are like
topographical elevation contour maps, in that no two contour lines
should every cross and in that all the contour lines should close.
Consequently, the loops of contours enclose regions; and these
regions overlap in a nested fashion forming a tree like data
structure.
As the general examples of contoured images on page 5
illustrate, a notion that is emphatically not in CRE, is that of a
schematic line drawing. Although the CRE output can be viewed as a
collection of lines on a display screen, people expecting a line
drawing rendition of the given television picture will be
disappointed. A CRE picture is a simple transformation of the
photometry, geometry and topology of the original video image;
whereas the typical line drawing from a human illustrator is a
representation of the scene without photometric information. On the
other hand, the work of an artist such as Peter Max; or a
paint-by-the-numbers grid does resembly CRE output. This is not an
idle coincidance but rather a consequence of whether or not the
artist is trying to represent photometric data by quantum lines.
The explanation of CRE node structures will be presented in
three parts: first, the several kinds of nodes will be briefly
explained; second, the sub structures such as rings, trees and
lists will be discribed; and third, the node formats and their
contents will be explained in detail. Following that will be an
explanation of the five arrays in CRE. The reader is warned that
this whole sub section (on data structure) is an elaborate shaggy
dog story of naming names and defining things; all the action is to
be found in the following sub section (on the algorithm).
~I1973,835;F8- 6 -
DATA STRUCTURE: KINDS OF NODES.
The are eight kinds of CRE nodes: Vector, Arc, Polygon,
Shape, Image, Level, Film and Empty.
1. At the very top of all the structure is the film node, the film
node is unique and serves as an OBLIST from which all other nodes
may be reached. The film node embodies the idea of a piece of
celluloid film or a length of magnetic video tape. A film is a
sequence of images taken by the same camera of the same scene with
only a small amount of action between images.
2. An image node represents the familiar two dimensional idea of a
photograph or an oil painting or to be exact a digital video image
of 216 rows by 288 columns of numbers ranging from 0 for dark to 63
for bright. The image is formed by a thin lens and is projected on
a flat image plane. The idea of an image is so common that it is
easy to overlook the wonder of sun light scattering off of surfaces,
refracting thru a lens, and forming a complex pattern called a real
image.
3. Below the image node are the intensity contour levels. A contour
level is a binary image that results from thresholding a gray scaled
image. So an image is composed of levels, and in turn, a level is
composed of polygons.
4. A Polygon node represents the idea of a contour loop which
always closes upon itself and does not cross itself or any other
contour. Contour loops are approximated by a ring of vectors; hence,
the term "polygon". The contour polygons always have at least three
sides and are simply connected.
5. Shape nodes contain data about one or two polygons. The data in a
shape node is not a positive representation of the notion of shape;
but is rather the parameters of allignment and normalization that
must be compensated before shapes can be compared.
6. Vector nodes contain the locus of an image vertex; however since
vectors always belong to a polygon and always have two neighbors;
their counterclockwise neighbor is considered to determine their
vector direction.
7. Arc nodes are vectors that are made by the polygon smoothing
routine; one arc typically replace several vectors. When both arcs
and vectors are being discussed; vectors are strictly horizontal and
vertical, whereas arcs may point in any direction.
8. Empty nodes are an artifact of the fixed node size dynamic
storage allocation mechanism used in CRE. Entities are made by
taking empty nodes from an AVAIL list and entities are killed by
returning their node to the AVAIL list; there is no garbage
collector, but there is a space compactor.
~I1973,835;F8- 7 -
DATA STRUCTURE: LINK AND DATUM NAMES.
Nodes contain either numerical data or pointers to other
nodes; such node pointers are actual machine addresses and are
called links. The positions within a node where a link is stored are
named and are reserved for particular uses. In the table below the
11 link names and 13 datum names are introduced. The link names
will always appear capitalized.
11 LINK NAMES:
CW clockwise
CCW counter clockwise
DAD parent of node up a tree structure.
SON descendent of a node down a tree structure.
ENDO Greek for inside, polygon within.
EXO Greek for outside, surrounding polygon.
ALT alternate.
NGON negative polygon.
PGON positive polygon.
NTIME negative in real time, into the past.
PTIME positive in real time, into the future.
13 DATUM NAMES:
Boolean datums.
type type of node bits.
reloc rellocation of node bits.
Fixed point datums.
row row of image locus.
col column of image locus.
cntrst contrast of an edge, vector and arc.
ncnt number count, various uses.
Floating point datums.
zdepth z depth from camera lens center.
perm length of perimeter.
area area in pixel units.
mxx moment of inertia about X axis.
myy moment of inertia about Y axis.
mzz moment of inertia about Z axis.
pxy product of inertia with respect
to the X and Y axes.
~I1973,835;F8- 8 -
DATA STRUCTURE: THE RINGS, TREES, LISTS AND ARRAYS.
CRE inputs an image into an array called TVBUF; it makes the
node structures, some of which are temporary; and it outputs a final
version of the structure representing a film of images. The
temporary structures are relevant to understanding the process; but
only the final structure is relevant to using CRE output. In
summary, the important structures are:
FOUR RINGS.
1. Image ring of the film.
2. Level ring of an image.
3. Polygon ring of a level.
4. Vector ring of a polygon.
TWO TREES.
1. The tree of rings.
2. The tree of nested polygons.
TWO LISTS.
1. Time line lists.
2. The empty node list.
TEMPORARY STRUCTURES.
1. Arc rings of polygons.
2. Fusion shape rings of levels.
FIVE ARRAYS.
1. TVBUF - 216 rows, 288 columns of 6 bit bytes.
2. PAC - 216 rows, 288 columns of 1 bit bytes.
3. VSEG - 216 rows, 289 columns of 1 bit bytes.
4. HSEG - 217 rows, 288 columns of 1 bit bytes.
5. SKY - 216 rows, 289 columns of 18 bit bytes.
There is one film node. The film is composed of a ring of
images. Each image is composed of a ring of levels. Each level is
composed of a ring of polygons. Each polygon is composed of a ring
of vectors. The ring structures are implemented with the four links
named DAD, SON, CW and CCW. The rings are headless only in the
sense that all the elements of a ring are brothers; a pointer to the
head of a ring is stored in the DAD link of each element. The DAD of
the film node is NIL; and NIL is an 18-bit zero. The final SON of
all vector nodes is also NIL. The DAD and SON links form a tree of
rings.
~I1973,835;F8- 9 -
DATA STRUCTURE: THE RINGS, TREES, LISTS AND ARRAYS.
Besides the tree of rings, there is the tree of nested
polygons. The nested polygon tree is implemented with the four
links named ENDO, EXO, NGON and PGON. The EXO of a polygon points
at its surronding polygon. The ENDO of a polygon points at one of
the polygons that may be enclaved within the given polygon; and the
NGON and PGON links form a ring of polygons that have the same EXO
polygon.
The time line lists run thru arc and polygon nodes. In the
simple case, the time line links of a polygon point to a
corresponding polygon in the image previous (NTIME) or subsequent
(PTIME) of the current polygon. The correspondence being that the
time polygon is exactly the same intensity at nearly the same
location, orientation, and size as the given polygon. In the case of
polygon fusion, the time line link of a polygon points to a time
polygon of which the given polygon becomes a part. In the case of
polygon fission, the time line link of a polygon points to only one
the pieces into which the given polygon splits.
The time line links of an arc vector point to a
corresponding arc vector in the image previous or subsequent of the
current arc vector. The polygons of arc vectors mated in time are
also mated in time; because after polygon time line links have been
made, one polygon is temporarily translated, rotated and dilated so
as to have the same lamina inertia tensor as its mate; that is the
locus of the arc vectors of one polygon are temporarily altered;
then the corresponding arc vectors are found and their time line
linkages are made.
The empty node list is maintained in the CCW link positions;
the last empty node contains a zero link. All nodes are explicitly
made from and killed to the empty node list by the subroutines
MKNODE and KLNODE.
The arc ring of a polygon is just like a vector ring except
that the pointer to it is stored in the ALT link of the polygon,
while the polygon has both a ring of vectors and a ring of arcs.
The fusion shape ring of a intensity level runs thru the CW
and CCW links of shape nodes and is pointed at by the ALT link of
the level. Fusion shape nodes are the shapes generated to represent
pairs of polygons unmated in time.
~I1973,835;F8- 10 -
DATA STRUCTURE: TYPE BITS.
Each node has a word reserved for a boolean vector of 36
values, or bits. The first eighteen bits are called the type bits
and are individually named as follows:
_____________________________________________________________________
for 0 WESBIT westward vector.
vectors 1 SOUBIT southward vector.
only 2 EASBIT eastward vector.
3 NORBIT northward vector.
_____________________________________________________________________
4 NFUSE NTIME polygon fusion.
5 NFISS NTIME polygon fission.
for 6 NEXCT NTIME polygon exact match.
polygons
only 7 PFUSE PTIME polygon fusion.
8 PFISS PTIME polygon fission.
9 PEXCT PTIME polygon exact match.
_____________________________________________________________________
10 HOLBIT Hole polygon bit.
modify 11 ARCBIT Arc vector bit.
_____________________________________________________________________
12 SBIT Shape node bit.
13 VBIT Vertex node bit.
14 PBIT Polygon node bit.
kind
15 LBIT Level node bit.
16 IBIT Image node bit.
17 FBIT Film node bit.
_____________________________________________________________________
The first four bits WESBIT, SOUBIT, EASBIT and NORBIT apply
only to vectors and indicate the direction of the vector. The next
six bits NFUSE, NFISS, NEXCT, PFUSE, PFISS, PEXCT are set by the
polygon compare routine to indicate the kind of time mating found;
where N and P mean negative time or postive time linkage; fusion
means that the given polygon and another polygon fuse to form the
time polygon, two into one; fission means the given polygon splits,
one into two; and exact means that the given polygon matchs one for
one with its time polygon.
The next two bits HOLBIT and ARCBIT indicate distinguished
polygons and vectors respectively. Only one of the last six bits:
SBIT, VBIT, PBIT, LBIT, IBIT and FBIT may be on in a node. These
bits indicate the node's type.
~I1973,835;F8- 11 -
DATA STRUCTURE: RELLOCATION BITS.
The next eighteen bits are called the reloc bits and
indicate whether or not a link is stored in a particular position of
the node. The rellocation bits are used to compact the CRE node
space for output.
18 unused
19 CAR(WORD0)
20 CDR(WORD0)
21 unused
22 CAR(WORD1)
23 CDR(WORD1)
24 unused
25 CAR(WORD3)
26 CDR(WORD3)
27 unused
28 CAR(WORD4)
29 CDR(WORD4)
30 unused
31 CAR(WORD5)
32 CDR(WORD5)
33 unused
34 CAR(WORD6)
35 CDR(WORD6)
The CAR of a word is the left half. The CDR of a word is the
right half. In the node diagrams the rellocation of each word is
indicated directly to its right as 0, 1, 2 or 3 meaning no
rellocation, left only, right only, and rellocate both halves,
respectively.
~I1973,835;F8- 12 -
1. VECTOR & 2. ARC NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | vector ring | 3
_____|___________________|___________________|
word | DAD | SON |
1 | polygon | arc or vector | 3
_____|___________________|___________________|
word | type | reloc |
2 | | 33 0003 |
_____|___________________|___________________|
word | row | col |
3 | 0000.00 | 0000.00 | 0
_____|___________________|___________________|
word | cntrst | ncnt |
4 | | length | 0
_____|___________________|___________________|
word | |
5 | zdepth | 0
_____|_______________________________________|
word | | |
6 | NTIME time line PTIME | 3
_____|___________________|___________________|
The format of vectors and arcs is identical. Inside CRE the
term "vector" has the connotation of being strictly a horizontal or
vertical generated by the contouring step; whereas an arc is a
vector generated by the smoothing step. Vectors contain the
fundamental geometric datum of an image locus. The image locus is
stored in the halfword datums named row and col, which contain the
row and column of a point in units 1/64 of a pixel. (A "pixel" is a
"picture element"). Vectors and arcs also contain the photometric
datum of edge contrast.
Vectors always belong to a polygon node, a pointer to the
polygon of each vector is stored in the link named DAD; as members
of a polygon the vectors form a loop which is always connected so that
each vertex has a neighboring vertex in the clockwise and in the
counter clockwise directions about the polygon's perimeter; these
perimeter pointers are stored in the link positions named CW and
CCW. Vectors never cross, arcs cross on occassions but can be fixed.
The ncnt datum of arcs and vectors contains their length.
The time line links, NTIME and PTIME, may point to a corresponding
arc or vector in the image previous or subsequent to the current
image. (The zdepth datum contains a positive number indicating
distance from the camera's image plane; the zdepth computation is
not properly implemented as of May 1973).
~I1973,835;F8- 13 -
3. POLYGON NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | polygon ring | 3
_____|___________________|___________________|
word | DAD | SON |
1 | level | 1st vector | 3
_____|___________________|___________________|
word | type | reloc |
2 | 10 | 33 3233 |
_____|___________________|___________________|
word | ENDO | EXO |
3 |1st polygon within |polygon surround me| 3
_____|___________________|___________________|
word | ALT | ncnt |
4 | shape {or 1st arc}| number of sides | 2
_____|___________________|___________________|
word | NGON | PGON |
5 | nest bro polygon | nest sis polygon | 3
_____|___________________|___________________|
word | | |
6 | NTIME time line PTIME | 3
_____|___________________|___________________|
Every polygon belongs to a level pointed at by the DAD link;
the ring of polygons of a level is formed in the CW and CCW links;
the son of a polygon is its first vector (or arc after the polygon
has been smoothed) and that first vector has the upper left most
locus of any vector of the polygon.
The ENDO, EXO, NGON, PGON are used to form the nested
polygon tree. Every polygon has non-NIL NGON and PGON links; the
trivial case being that the polygon points at itself twice. Every
polygon except one, the outer border polygon, has a non-NIL EXO
link. Every polygon that surrounds one or more other polygons has a
non-NIL ENDO link.
The ALT link position of a polygon temporarily points to the
first arc of a polygon during smoothing when a polygon has both
vectors and arcs. The final contents of the ALT link is a pointer to
the shape node of the polygon. The ncnt datum indicates the number
of sides of the polygon.
The time line of polygons runs thru the NTIME and PTIME
links which point either to a nearly exact match of a polygon; or to
a fusion polygon of a two for one match; or to one of the two
fission parts of a one for two match; (to find the other fission
part, the time links of the vectors must be scanned).
~I1973,835;F8- 14 -
4. SHAPE NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | fusion shape ring | 3
_____|___________________|___________________|
word | perm | area |
1 | | | 0
_____|___________________|___________________|
word | type | reloc |
2 | 10 | 30 0030 |
_____|___________________|___________________|
word | row | col |
3 | 0000.00 | 0000.00 | 0
_____|___________________|___________________|
word | pxy | mzz |
4 |product of inertia | Z-axis moment | 0
_____|___________________|___________________|
word | NGON | PGON |
5 | fusion polygon | main polygon | 3
_____|___________________|___________________|
word | mxx | myy |
6 | X-axis moment | Y-axis moment | 0
_____|___________________|___________________|
The shape node contains the data necessary for normalizing
two polygons so that only their shapes remain. In particular, the
row and col of a shape node is the center of mass of the polygon;
area is the area; perm is the length of perimeter; and mxx, myy,
mzz, pxy is the polygons inertia tensor (from which the principle
angle of orientation can be computed). When given two shapes, the
centers of mass may be alligned; the principle angles may be allign;
and the areas (or permeter) of the two may be normalized.
There are two kinds of shapes: polygon shapes and fusion
shapes. Polygon shapes correspond to a single polygon pointed at by
the PGON link. The CW, CCW and NGON links of a polygon shape are
NIL. Fusion shapes are temporary nodes belonging to a level as a
ring thru CW and CCW. Fusion shapes correspond to the summation of
two unmated polygons which are pointed to by the NGON and PGON
links. The expressions relating to the inertia tensor and to fusion
summation are given in the section on polygon comparing.
The datums named perm, area, pxy, mxx, myy, mzz contain the
left half of a PDP-10 floating number. (Technical note: half of a
floating number has 9 bits of precision and should be expanded to
full word by using the (mirabile dictu !) HLLE instruction in order
to avoid an illegal floating zero caused by truncating numbers like
-1023.0; in CRE, only the product of inertia will ever be negative).
~I1973,835;F8- 15 -
5. LEVEL NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | level ring | 3
_____|___________________|___________________|
word | DAD | SON |
1 | image | 1st polygon | 3
_____|___________________|___________________|
word | type | reloc |
2 | | 33 0200 |
_____|___________________|___________________|
word | | |
3 | --- | --- | 0
_____|___________________|___________________|
word | ALT | ncnt |
4 | (1st fusion shape)|threshold cut level| 2
_____|___________________|___________________|
word | | |
5 | --- | --- | 0
_____|___________________|___________________|
word | | |
6 | --- | --- | 0
_____|___________________|___________________|
Every level belongs to an image pointed to by the DAD link;
the ring of levels of an image is formed in the CW and CCW links;
the son of a level is its first polygon and that first polygon is
the upper left most polygon of the level.
The ncnt datum of a level contains its threshold cut value,
which is an integer between -1 and 63. The -1 level is always
generated, and it contains a single polygon with four sides. The -1
level's polygon is called the border polygon; the fiction being that
every point beyond the edges of the televsion picture has an
intensity value of -2, which is blacker than black.
The ALT link of a level contains a temporary pointer to that
level's ring of fusion shapes during polygon compare time mating.
~I1973,835;F8- 16 -
6. IMAGE NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | image ring | 3
_____|___________________|___________________|
word | DAD | SON |
1 | film | 1st level | 3
_____|___________________|___________________|
word | type | reloc |
2 | | 33 0000 |
_____|___________________|___________________|
word | | |
3 | --- | --- | 0
_____|___________________|___________________|
word | | |
4 | --- | --- | 0
_____|___________________|___________________|
word | | |
5 | --- | --- | 0
_____|___________________|___________________|
word | | |
6 | --- | --- | 0
_____|___________________|___________________|
Every image belongs to the film pointed to by the DAD link;
the ring of images of the film is formed in the CW and CCW links;
the son of an image is its first level and that first level is the
-1 intensity cut level of the image.
Although an affront to common sense, the counter clockwise
direction about the image ring is positive or later in time and the
clockwise direction is negative or earlier in time. I achieved this
curio by consistently adhereing to the mathematical convention of
counter clockwise as positive; and a day came when counter clockwise
around a ring of real time events was represented in the same manner
as counter clockwise around a polygonal ring of edges.
All the empty space in the image node is reserved for camera
specification data.
~I1973,835;F8- 17 -
7. FILM NODE FORMAT.
_____________________________________________
word | | CCW |
0 | | 1st empty | 1
_____|___________________|___________________|
word | DAD | SON |
1 | 0 | 1st image | 3
_____|___________________|___________________|
word | type | reloc |
2 | | 33 0000 |
_____|___________________|___________________|
word | | |
3 | --- | --- | 0
_____|___________________|___________________|
word | | |
4 | --- | --- | 0
_____|___________________|___________________|
word | | |
5 | --- | --- | 0
_____|___________________|___________________|
word | | |
6 | --- | --- | 0
_____|___________________|___________________|
The film node is unique; it is the first node in a CRE
output file; the SON of film is its first image; the DAD of a film
is NIL; the CCW of a film is a pointer to the 1st empty node;
however, because the nodes are compacted for output and then
relocated with respect to the film node; the final empty node
pointer indicates the number of words of data in the CRE file.
~I1973,835;F8- 18 -
8. EMPTY NODE FORMAT.
_____________________________________________
word | | CCW |
0 | --- | avail | 1
_____|___________________|___________________|
word | | |
1 | --- | --- | 0
_____|___________________|___________________|
word | type | reloc |
2 | | 00 0000 |
_____|___________________|___________________|
word | | |
3 | --- | --- | 0
_____|___________________|___________________|
word | | |
4 | --- | --- | 0
_____|___________________|___________________|
word | | |
5 | --- | --- | 0
_____|___________________|___________________|
word | | |
6 | --- | --- | 0
_____|___________________|___________________|
The list of empty nodes is maintained in the CCW link
postion; the last empty node contains a zero or NIL link. At present
all the other words of an empty node are zero.
FIGURE SHOWING RASTER STRUCTURE._____________________________________
↑
↑
NORTH
grid point R,C R,C+1
o____HSEG______o
|
|
|
←←←WEST VSEG PIXEL(R,C) EAST→→→
|
|
|
o SOUTH
R+1,C ↓
↓
_____________________________________________________________________
~I1973,835;F8- 19 -
DATA STRUCTURE: IMAGE ARRAYS.
There are five arrays in CRE: TVBUF, Television Buffer; PAC,
Picture Accumulator; VSEG, vertical segments; HSEG, horizontal
segments; and SKY, background sky blue array. The dimensions are:
FIVE ARRAYS.
1. TVBUF - 216 rows, 288 columns of 6 bit bytes.
2. PAC - 216 rows, 288 columns of 1 bit bytes.
3. VSEG - 216 rows, 289 columns of 1 bit bytes.
4. HSEG - 217 rows, 288 columns of 1 bit bytes.
5. SKY - 216 rows, 289 columns of 18 bit bytes.
Inside CRE, the video image size was fixed at 216 rows of
288 columns of 6 bits per pixel. My original idea was to write a
vision operator that would be applied on a small fixed sized window;
so I have had windows 2 by 2; 2 by 3; 4 by 9; 32 by 36; 72 by 96;
and 216 by 288. That is 216=2*2*2*3*3*3 and 288=2*2*2*2*2*3*3.
Having a fixed window size avoids a morass of word packing, array
allocation and window splicing. Having a window size constructed
out of powers of 2 and 3 simplifies what word packing is required
and allows me to do area and space computations in my head.
The image arrays of CRE are of course two dimensional with
the coordinates in row and columns. Row number increases going down
image, in the negative Y axis direction, which is also called the
direction south. Column numbers increase going right on the image,
in the positive X axis direction, which is also called the direction
east. Video picture elements, or "pixels" are thought of as
expressing the intensity of a square cell; the cells are numbered
from 0 to 215 rows, 0 to 287 columns; the number of a cell is the
grid locus of its upper left (northwest) corner; the center locus of
a cell is at (row+1/5,col+1/2). A pixel cell is surrounded by four
segments; the horizontal segments are numbered 0 to 216 rows, 0 to
287 columns; the number of an HSEG is the grid locus of its left
(west) end point. The vertical segments are numbered 0 to 215 rows,
0 to 288 columns; the number of a VSEG is the grid locus of its
upper (north) end point. These conventions are suggested in the
diagram at the bottom of page 19. ~I1973,835;F8- 20 -